#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string.h>
// 求数组长度
#define ARR_LEN(arr) (sizeof(arr) / sizeof(arr[0]))
// 交换数组中的两个元素
#define SWAP(arr, i, j ) {			\
	int tmp = arr[i];			\
	arr[i] = arr[j];			\
	arr[j] = tmp;			\
}

/*
	简单二分查找:
	查找目标值target在数组arr中的下标, 如果找到了就立刻返回它的下标
	思考:
	1.这个target是数组中第一个target吗?	不一定
	1.这个target是数组中最后一个target吗?	不一定

	思路:
	1.找到数组的中间值mid
	2.比较mid和target的大小关系:
		如果target > mid, 说明目标值在数组的右边区间, 于是丢弃掉整个左边区间, 去右半区间继续查找
		如果target < mid, 说明目标值在数组的左半区间, 于是丢弃掉整个右边区间, 去左半区间继续查找
		如果target = mid, 说明目标值就是数组的中间元素, 直接返回这个元素的下标
	3.以上操作肯定不可能一直折半区间,当区间没有一个元素时,查找就结束了,而且是没有找到target

	以上就是简单二分查找的算法思想

	原地算法
	分析一下算法的时间复杂度:
	O(logn)

	用什么办法实现呢?
	1.递归实现
	2.循环迭代
*/


/*
	递归分解的思路:
	找到中间值,然后比较,根据比较结果递归的查找另一半的区间
	递归的出口: 当区间不存在,没有任何元素时,递归结束
*/
static int bs(int arr[], int left, int right, int target) {
	// 递归的出口
	if (left > right) {
		// target不存在,返回不存在的下标
		return -1;
	}
	// 递归体
	int mid = left + (right - left >> 1);
	int diff = target - arr[mid];	// 注意:这里最好计算target-arr[mid] 不要反过来
	if (diff > 0) {
		// 递归查找右边区间,左半区间丢弃
		return bs(arr, mid + 1, right, target);
	}
	if (diff < 0) {
		// 递归查找左边区间,右半区间丢弃
		return bs(arr, left, mid - 1, target);
	}
	// 运行到这里,说明diff就等于target,找到了目标值
	return mid;
}

// 利用辅助函数完成递归折半查找
int bs_recursion(int arr[], int len, int target) {
	return bs(arr, 0, len - 1, target);
}

int bs_loop(int arr[], int len, int target) {
	int left = 0, right = len - 1;	// 循环折半的左右区间

	while (left <= right) {	// 只要区间当中还有一个元素,就继续循环二分查找
		int mid = left + (right - left >> 1);
		int diff = target - arr[mid];
		if (diff > 0) {
			// 循环的去查找右边区间,左半区间丢弃,要改left
			left = mid + 1;
		}
		else if (diff < 0) {
			// 循环的去查找左边区间,右半区间丢弃,要改right
			right = mid - 1;
		}
		else {
			// 找到了目标值
			return mid;
		}
	}
	// 循环都结束了,还没有return 说明目标值不存在
	return -1;
}

int main(void) {
	int arr[] = { 1,2,3,4,5,6,7,8,10,10,10,10,11,12,13,15,17,19,20 };
	int len = ARR_LEN(arr);
	//int ret = bs_recursion(arr, len, 10);
	int ret = bs_loop(arr, len, 10);
	return 0;
}